Skip to main content

第40章 递推算法

递推算法是一种通过已知条件逐步推导出未知结果的算法思想，它利用问题本身所具有的递推关系，从初始状态出发，按照一定的规律迭代计算，最终得到问题的解。

40.1 递推算法的基本概念​

递推算法的核心是递推关系，即问题的第nn项结果与前面若干项结果之间存在的确定关系。 通过这种关系，可以从已知的初始项（边界条件）出发，逐步计算出任意目标项。

递推关系数学形式： f(n)=g(f(n−1),f(n−2),...,f(n−k))f(n)=g(f(n-1), f(n-2), ..., f(n-k)) kk代表递推阶数； 初始条件：f(0),f(1)...f(0),f(1)...等已知固定值，无初始条件无法启动递推。

示例：斐波那契数列 递推关系：f(n)=f(n−1)+f(n−2)f(n)=f(n-1)+f(n-2) 初始条件：f(0)=0, f(1)=1f(0)=0,\ f(1)=1

40.2 递推算法核心思想​

  1. 分析问题，提炼递推公式；
  2. 确定初始边界值；
  3. 循环迭代，从已知项逐步计算到目标项； 全程仅循环，无递归调用，无栈开销。

40.3 递推标准代码框架​

// 1. 初始化初始条件 f(0),f(1)...
初始化前k项已知值;
// 2. 循环递推计算
for(int i = k; i <= n; i++){
    f[i] = 递推公式(f[i-1], f[i-2]...);
}
// 3. 输出目标项结果
return f(n);

40.4 递推两大分类​

40.4.1 顺推法（从前往后）​

从已知初始值出发，逐步向后计算目标值，最常用。 示例：斐波那契数列顺推

int fibonacci(int n){
    if(n == 0) return 0;
    if(n == 1) return 1;
    int a = 0; // f(0)
    int b = 1; // f(1)
    int res;
    for(int i = 2; i <= n; i++){
        res = a + b;
        a = b;
        b = res;
    }
    return b;
}

40.4.2 逆推法（从后往前）​

已知最终结果，反向倒推初始状态。 示例：存款逆推，已知n年后存款，求初始本金 设年利率rr，顺推公式 f(n)=f(n−1)∗(1+r)f(n)=f(n-1)*(1+r) 逆推公式 f(n−1)=f(n)/(1+r)f(n-1)=f(n)/(1+r)

double calculatePrincipal(double target, int n, double r) {
    double f = target;
    for(int i = n; i > 0; i--){
        f = f / (1 + r);
    }
    return f;
}

40.5 典型递推例题​

40.5.1 阶乘计算​

递推式：n!=n×(n−1)!n! = n \times (n-1)! 初始：0!=10! = 1

int factorial(int n){
    int res = 1;
    for(int i = 1; i <= n; i++){
        res *= i;
    }
    return res;
}

40.5.2 杨辉三角​

递推公式：C(i,j)=C(i−1,j−1)+C(i−1,j)C(i,j)=C(i-1,j-1)+C(i-1,j) 边界：每行首尾C(i,0)=1, C(i,i)=1C(i,0)=1,\ C(i,i)=1

#include <iostream>
using namespace std;
void yanghuiTriangle(int numRows) {
    int triangle[numRows][numRows];
    for(int i = 0; i < numRows; i++){
        triangle[i][0] = 1;
        triangle[i][i] = 1;
        for(int j = 1; j < i; j++){
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
        }
        // 打印一行
        for(int j = 0; j <= i; j++){
            cout << triangle[i] << " ";
        }
        cout << endl;
    }
}
int main(){
    yanghuiTriangle(5);
    return 0;
}

40.5.3 爬楼梯​

一次爬1或2级，到达第nn级的方案数 递推：f(n)=f(n−1)+f(n−2)f(n)=f(n-1)+f(n-2) 初始：f(1)=1, f(2)=2f(1)=1,\ f(2)=2

int climbStairs(int n) {
    if(n == 1) return 1;
    if(n == 2) return 2;
    int a = 1, b = 2, res;
    for(int i = 3; i <= n; i++){
        res = a + b;
        a = b;
        b = res;
    }
    return b;
}

40.6 复杂度分析​

  1. 时间复杂度：O(n)O(n)，循环仅执行nn次；
  2. 空间复杂度：
    • 仅保存前几项（斐波那契）：O(1)O(1)；
    • 存储全部中间结果（杨辉三角）：O(n2)O(n^2)。

40.7 递推 vs 递归​

对比项递推递归
执行方式循环迭代，从前向后计算函数自调用，拆分问题
性能无函数调用开销，速度快多层调用有额外开销，朴素斐波那契存在大量重复计算
空间开销可优化至O(1)O(1)递归栈深度O(n)O(n)，深度过大会栈溢出
可读性需手动推导迭代公式数学递归定义天然匹配，逻辑直观
适用场景大规模数据、避免栈溢出小规模、天然递归结构（树、汉诺塔）

40.8 使用注意事项​

  1. 准确推导递推关系式；
  2. 正确设置初始边界值，否则全部结果错误；
  3. 高阶递推仅保留必要前项，节省空间；
  4. 数值较大时注意int溢出，改用long long；
  5. 区分顺推、逆推场景。